package com.lin.maxsubarray;

/**
 * @author 九分石人
 */
public class MaxSubArray {


    /**
     * 使用动态规划的方法
     *
     * @param nums
     * @return
     */
    public static int maxSubArray(int[] nums) {
        int pre = 0;
        int max = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            max = Math.max(max, pre);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] nums = {-8, 1, 9, -3, 7, -6, 3};
        int i = maxSubArray(nums);
        System.out.println(i);
    }
}
